a) Igazolja, hogy az A(0 1), B(4 2), C(3 6) és D(-5 4) pontokkal megadott négyszög trapéz! b) Kati megrajzolt egy olyan egyszerű teljes gráfot, amelynek 253 éle van, és csúcsai között szerepelnek a trapéz A B C D csúcsai is. Hány új gráfcsúcsot kellett ehhez felvennie? Legfeljebb hány éle törölhető ki ennek a teljes gráfnak, hogy még összefüggő maradjon?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1296

Öt, egymástól távol eső tanya között kábeleket feszítenek ki, bármely két tanya között legfeljebb egyet. a) Elvileg összesen hány különböző hálózatot lehetséges létrehozni a tanyák kö- zött? (A hálózatban a kifeszített kábelek száma 0-tól 10-ig bármennyi lehet. Két hálózatot akkor tekintünk különbözőnek, ha van olyan összeköttetés, amely az egyikben létezik, de a másikban nem.) b) Takarékossági okokból csak 4 kábelt feszítenek ki úgy, hogy a hálózat azért összefüggő legyen. (Összefüggőnek tekintünk egy hálózatot, ha a kábelek men- tén bármely tanyáról bármely másikba el lehet jutni, esetleg más tanyák közbeik- tatásával.) Hány különböző módon tehetik ezt meg, ha az egyes tanyákat megkü- lönböztetjük egymástól?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1363

a) A következő két állításról döntse el, hogy igaz vagy hamis. Válaszait indokolja! (1) Van olyan ötpontú egyszerű gráf, amelynek 11 éle van. (2) Ha egy ötpontú egyszerű gráf minden csúcsa legalább harmadfokú, akkor biztosan van negyedfokú csúcsa is. b) Az A, B, C, D és E pontok egy ötpontú teljes gráf csúcsai. A gráf élei közül véletlenszerűen beszínezünk hatot. Mekkora a valószínűsége annak, hogy az A, B, C, D, E pontokból és a színezett élekből álló gráf nem lesz összefüggő?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1408

Tekintsük a következő, egyszerű gráfokra vonatkozó állítást: Ha a gráf minden pontjának fokszáma legalább 2, akkor a gráf biztosan összefüggő. a) Döntse el, hogy igaz vagy hamis az állítás! Válaszát indokolja! b) Fogalmazza meg az állítás megfordítását! Döntse el, hogy igaz vagy hamis az állí- tás megfordítása! Válaszát indokolja! Tekintsük a következő halmazokat: P = {összefüggő gráfok}, Q = {egyszerű gráfok}, R = {kört tartalmazó gráfok}. c) Helyezze el az alábbi gráfok ábrájának sorszámát a fenti halmazábrában a megfele- lő helyre! 1. ábra 2. ábra 3. ábra 4. ábra d) Rajzoljon egy 6 pontú fagráfot az 5. ábrára, és helyezze el ennek a sorszámát is a fenti halmazábrában a megfelelő helyre!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1417

a) Határozza meg az alábbi kijelentések logikai értékét (igaz-hamis)! Válaszait indokolja! I. Van olyan hatpontú fagráf, amelynek minden csúcsa páratlan fokszámú. II. Ha egy hétpontú egyszerű gráfnak 15 éle van, akkor a gráf összefüggő. III. Van olyan fagráf, amelyben a csúcsok számának és az élek számának összege páros. Egy hatfős társaság tagjai A, B, C, D, E és F. Mindenkit megkérdeztünk, hogy hány is- merőse van a többiek között (az ismeretség kölcsönös). A válaszként kapott hat termé- szetes szám szorzata 180. Az is kiderült, hogy A-nak legalább annyi ismerőse van, mint B-nek, B-nek legalább annyi ismerőse van, mint C-nek, és így tovább, E-nek legalább annyi ismerőse van, mint F-nek. b) Szemléltesse egy-egy gráffal a lehetséges ismeretségi rendszereket!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1497

A H halmaz a nyolcpontú egyszerű gráfok halmaza. A következő állítás a H elemeire vonatkozik: Ha egy (nyolcpontú egyszerű) gráf minden pontjának fokszáma legalább 3, akkor a gráf összefüggő. a) Döntse el, hogy az állítás igaz vagy hamis! Válaszát indokolja! b) Fogalmazza meg az állítás megfordítását a H elemeire vonatkozóan, és döntse el a megfordított állításról, hogy igaz vagy hamis! Válaszát indokolja! Az ABCDE konvex ötszög csúcsait piros, kék vagy zöld színűre színezzük úgy, hogy bármely két szomszédos csúcsa különböző színű legyen. c) Hány különböző színezés lehetséges? (Az ötszög csúcsait megkülönböztetjük egymástól.) Egy négypontú teljes gráf élei közül véletlenszerűen kiválasztott négy élt kiszínezünk zöldre. (Teljes gráf: olyan egyszerű gráf, melynek bármely két pontja között van él.) d) Határozza meg annak a valószínűségét, hogy a zöldre színezett élek a gráf egy négypontú körének élei!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 1540

Az ábrán egy 3×3-as kirakós játék (puzzle) sematikus képe látható. A kirakós játékot egy gráffal szemléltethetjük úgy, hogy a gráf csú- csai (A1, A2, ... , C3) a puzzle-elemeket jelölik, a gráf két csúcsa között pedig pontosan akkor vezet él, ha a két csúcsnak megfelelő puzzle-elemek közvetlenül (egy oldalban) kapcsolódnak egymás- hoz a teljesen kirakott képben. a) Rajzolja fel a kirakós játék gráfját (a csúcsok azonosításával együtt), és határozza meg a gráfban a fokszámok összegét! b) Igazolja, hogy a megrajzolt gráfban nincs olyan (gráfelméleti) kör, amely páratlan sok élből áll! c) A teljesen kirakott képen jelöljön meg a puzzle-elemek közül 7 darabot úgy, hogy a kirakósjáték általuk alkotott részlete (a részletnek megfelelő gráf) már ne legyen összefüggő! d) Hányféleképpen lehet a puzzle-elemek közül hármat úgy kiválasztani, hogy ezek a teljesen kirakott képben kapcsolódjanak egymáshoz (azaz mindhárom képrészlet közvetlenül kapcsolódjék legalább egy másikhoz a kiválasztottak közül)? (Az elemek kiválasztásának sorrendjére nem vagyunk tekintettel.)

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 7702

Öt különböző számjegyet leírunk egy papírlapra. Két számjegyet pontosan akkor kötünk össze egy vonallal (éllel), ha a különbségük páros szám (de egyik számjegyet sem kötjük össze önmagával). Így egy ötpontú gráfot kapunk. a) Határozza meg az alábbi két állítás logikai értékét (igaz vagy hamis)! Válaszát indokolja! I. Lehetséges, hogy fagráfot kapunk. II. Lehetséges, hogy nem összefüggő gráfot kapunk. Az Óceán Légitársaságnak a megalakulása óta alapelve, hogy a szigetvilágban működő hálózatának bármely két célállomása között működtet repülőjáratot. (Az ábra azt a több évvel ez- előtti időszakot szemlélteti, amikor még csak négy célállomás és hat repülőjárat volt.) A hálózatot folyamatosan bővítik: az utóbbi két év alatt a cél- állomások száma másfélszeresére nőtt, ugyanezen idő alatt a repülőjáratok száma pedig 60-nal lett több. b) Hány célállomásra közlekednek jelenleg? A légitársaság vezetőségi értekezletén megállapították, hogy az 1-es számú járatukon leg- feljebb 168 utasnak van hely, de minden alkalommal sokkal többen szeretnének jegyet váltani. Több év tapasztalatai szerint 0,032 annak a valószínűsége, hogy erre a járatra valaki megveszi a jegyet, de aztán valamilyen ok miatt mégsem jelenik meg a járat indu- lásánál. Emiatt a vezetőség úgy dönt, hogy erre a 168 fős járatra ezentúl 170 jegyet adnak el. Az érvényes szabályozás szerint a több jegy eladása miatt a járatról esetleg lemaradó utasoknak a légitársaság fejenként 600 euró kártérítést köteles fizetni. c) Ha a vezetőség megállapításai helyesek, akkor mennyi a valószínűsége annak, hogy az 1-es számú járat egy indulásánál legfeljebb 168 utas jelenik meg, és mennyi a társaság által fizetendő kártérítés várható értéke a járat egy útját tekintve?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 8942

Több település közötti legkisebb költségű vezetékhálózat tervezésekor először egy teljes gráfot készítettek. Ebben a gráfban minden települést a gráf egy csúcsával, minden ve- zetékes kapcsolatot a gráf egy-egy élével jelöltek, majd a gráf minden élére ráírták, hogy mennyibe kerülne az adott kapcsolat kiépítése. Ezután egyesével kitörölték a költséges éleket úgy, hogy a törlés után megmaradó gráf összefüggő maradjon. A teljes gráf élei kétharmadának törlése után végül egy (a legkisebb költségű hálózatot megadó) fagráfot kaptak. a) Hány település szerepelt a tervben? Az őszi kispályás labdarúgó bajnokságban 10 település egy-egy csapata vett részt. Min- den csapat egy mérkőzést játszott mindegyik másik csapattal minden mérkőzés győztese 3, vesztese 0 pontot kapott, döntetlen esetén mindkét csapatnak 1-1 pont járt. A bajnokság végén a 10 csapatnak összesen 130 pontja volt. b) Hány mérkőzés végződött döntetlenre?

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 8952

Legyen az U alaphalmaz a legalább 4 pontú egyszerű gráfok halmaza. Az F halmaz az U elemei közül pontosan azokat tartalmazza, amelyek fagráfok, a G halmaz pontosan azo- kat, amelyek összefüggő gráfok, a H halmaz pedig pontosan azokat, amelyek 6 pontú gráfok. a) Az alábbi ábrán satírozással jelölje meg, és halmazműveletekkel is adja meg az U-nak azt a részhalmazát, amelyik üres halmaz! b) A megadott Venn-diagram minden egyes további részébe rajzoljon pontosan egy lehetséges gráfot! Egy telephely K, L, M, N, O, P, Q épületei közül az éjszakai első ellenőrzés során ötöt ellenőriz a biztonsági őr. c) Hányféleképpen tervezheti meg az útvonalát, ha a K és L épületeket mindenképpen ellenőrzi? (Két útvonal különböző, ha a két út során más épületeket, vagy ugyan- azokat az épületeket, de más sorrendben ellenőriz a biztonsági őr.) Megrajzoltuk az ABCDE konvex ötszög oldalait és átlóit, majd a megrajzolt szakaszok mindegyikét vagy kékre, vagy zöldre színeztük. A színezés befejezése után észrevettük, hogy nincs olyan háromszög, amelynek csúcsai az A, B, C, D, E pontok közül valók, és mindhárom oldala azonos színű. d) Igazolja (például indirekt módszerrel), hogy nincs olyan csúcsa az ötszögnek, amelyből legalább három azonos színű szakasz indul ki!

Az appot fejleszti: Vántus András | Kecskemét, 20/424-89-36 | matematica.hu | A feladatok az Oktatási Hivatal honlapjáról származnak. | 8971